P 复杂度类

阐述

P 是可以用一个确定性单纸带 Turing 机在多项式时间内判定的问题的集合。

$$\mathrm{P}=\bigcup_{k} \operatorname{TIME}\left(n^{k}\right)$$

由于时间复杂度#确定性计算模型的多项式等价性，P 对这些模型都是相同的。

在描述 P 相关的算法时，我们需要做两件事：

1. 对算法的阶段数量提供一个多项式上界；
2. 对每个阶段确保它能在多项式时间内实现。

实例

$$P A T H=\{\langle G, s, t\rangle \mid G \text { is a directed graph that has a directed path from } s \text { to } t\}$$ $$RELPRIME=\{\langle x, y\rangle \mid x \text { and } y \text { are relatively prime }\}$$

如果 A 是一个 CFL，那么 A 属于 P。

性质

相关内容

参考文献